#ifndef _tree2d_h_
#define _tree2d_h_

#include <typelib/types.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <limits>

// A version of kDimTree that is specialized for 2d points and 
// behaves like true container (not reference-container)

namespace xtd {

template <class T> class static_typecast {
public:
	template <class C> T operator () (const C & value) const
		{ return static_cast<T>(value); }

};

template <class T> class dereferencing_typecast {
public:
	template <class C> T operator () (const C * ptr) const
		{ return static_cast<T>(* ptr); }
};

class range_finder : public std::binary_function<point<double>, point<double>, double> 
{
public:
	double operator () (point<double> const & p1, point<double> const & p2) const
		{ return square(p1 - p2); }
	double operator () (double c1, double c2) const
		{ return square(c1 - c2); }
};

// T is convertable to P through C (custom typecast)
template <class T, class P = point<float>, class R = rect<float>, class C = static_typecast<P> >
class tree2d {
public:
    typedef size_t size_type;
	typedef T value_type;
	typedef C cast_type;
	typedef P point_type;
	typedef R rect_type;
public:
	// iterator that traverses all nodes in given range
	class range_iterator;
	class iterator;
	class const_iterator;
public:
	tree2d(const cast_type & c = cast_type());
	template <class I>
	tree2d(I first, I last, const cast_type & c = cast_type());
	~tree2d();
public:		 
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;
	range_iterator range_begin(const rect_type & r) const;
	range_iterator range_end() const;
	bool empty() const;
	size_type size() const;
	size_type capacity() const;
	cast_type & cast() const;
	void push_back(const value_type & v);
	template <class I>
	void assign(I first, I last);
	void erase(const_iterator it);
	void clear();
	void reserve(size_type n);
	void rebalance();
	template <class D>
	const_iterator nearest(const point_type & p, 
		D const & range_finder = xtd::range_finder(),
		typename D::result_type distance_threshold = std::numeric_limits<typename D::result_type>::max()) const;
private:
	static const size_type npos = size_type(-1);
private:
	class node; // 2d-tree node
	class less_x;
	class less_y;
	template <class D> class nearest_locator;
	typedef std::vector<node> node_vector;
private:
	size_type subtree(size_type first, size_type last, bool xnode);
	void insert(size_type root, size_type index);
private:
	node_vector		_nodes;
	size_type		_root;
	size_type		_removed;
	cast_type		_cast;
};

} //namespace xtd;

#include "impl/tree2d.inl"

#endif //_tree2d_h_
